package jm.data.structure.filter;

/**
 * @Description 布隆过滤器实现
 * @date 2022/5/26 20:16
 */
public class BloomFilter<T> {

    // 二进制向量长度
    private int bitSize;

    // 二进制向量 一个long元素 64 位
    private long[] bits;

    // 哈希函数个数
    private int hashSize;

    /**
     * 构造函数
     * @param n 数据规模
     * @param p 误判率
     */
    public BloomFilter(int n, double p) {
        if (n <= 0 || p <= 0 || p >= 1) {
            throw new IllegalArgumentException("parameter error");
        }

        double ln2 = Math.log(2);

        // 计算二进制向量长度
        bitSize = (int) (-(n * Math.log(p)) / (ln2 * ln2));

        // 计算哈希函数个数
        hashSize = (int) (bitSize * ln2 / n);

        // 确定数组长度
        bits = new long[(bitSize + Long.SIZE - 1) / Long.SIZE];
    }

    /**
     * 添加元素
     * @param v
     * @return
     */
    public boolean put(T v){
        nullCheck(v);

        // 计算 hash 值
        int h1 = v.hashCode();
        int h2 = hashSize >>> 16;

        boolean result = false;

        for (int i = 0; i < hashSize; i++) {
            // 根据两个 hash 计算当前hash
            int combinedHash = h1 + (i * h2);

            // 小于0 取反
            if (combinedHash < 0){
                combinedHash = ~combinedHash;
            }
            // 如果 hash 值过大，取模
            int index = combinedHash % bitSize;

            // 设置索引位置为1
            if (set(index)) result = true;
        }

        return result;
    }

    /**
     * 查询是否存在
     * @param v
     * @return
     */
    public boolean contains(T v){
        nullCheck(v);

        // 利用value生成2个整数
        int hash1 = v.hashCode();
        int hash2 = hash1 >>> 16;

        for (int i = 1; i <= hashSize; i++) {
            int combinedHash = hash1 + (i * hash2);
            if (combinedHash < 0) {
                combinedHash = ~combinedHash;
            }
            // 生成一个二进位的索引
            int index = combinedHash % bitSize;

            // 查询index位置的二进位是否为0
            if (!get(index)) return false;
        }
        return true;
    }

    /**
     * 参数检测
     * @param v
     */
    private void nullCheck(T v){
        if (v == null) {
            throw new IllegalArgumentException("v must be not null");
        }
    }

    /**
     * 设置index位置的二进位为1
     */
    private boolean set(int index) {

        // 根据当前索引获取数组中的元素
        long value = bits[index / Long.SIZE];

        // 计算当前位置位置的二进制值，除非当前索引位置是1外都是0
        int bitValue = 1 << (index % Long.SIZE);

        // 当前位置取反
        bits[index / Long.SIZE] = value | bitValue;

        // 判断是否已经存在
        return (value & bitValue) == 0;
    }

    /**
     * 查看index位置的二进位的值
     * @return true代表1, false代表0
     */
    private boolean get(int index) {
        long value = bits[index / Long.SIZE];
        return (value & (1 << (index % Long.SIZE))) != 0;
    }


}
